"""
交换列表中两个元素的位置
只能操作数字类列表
"""
def exchange_element(unsorted_list, index1, index2):
    unsorted_list[index1] += unsorted_list[index2]
    unsorted_list[index2] = unsorted_list[index1] - unsorted_list[index2]
    unsorted_list[index1] -= unsorted_list[index2]

"""
冒泡排序
此方法过于垃圾，不建议使用
@listA 需要排序的数据
"""
def bubble_sort(unsorted_list):
    for x in range(len(unsorted_list) - 1, 0, -1):
        for i in range(0, x):
            if unsorted_list[i] > unsorted_list[i + 1]:
                #交换两个元素的位置
                exchange_element(unsorted_list, i, i + 1)
    return unsorted_list

'''
插入排序
@listA 需要排序的数据
'''
def insert_sort(unsorted_list):
    #从第二个元素开始，逐个插入到之前的元素中
    for x in range(1, len(unsorted_list)):
        element = unsorted_list[x]
        #从x-1位开始比较
        for i in range(x - 1, -1, -1):
            if element < unsorted_list[i]:
                unsorted_list[i + 1] = unsorted_list[i]
                if i == 0:      #比到第一个元素仍然没插入到为止，说明当前元素是已知最小的，落到0位
                    unsorted_list[i] = element
            else:
                unsorted_list[i + 1] = element
                break
    return unsorted_list

'''
希尔排序
@listA 需要排序的列表
@group_length 分组进行排序，每组的元素数量
'''
def shell_sort(unsorted_list, group_length):
    #计算步长（同一组相邻两个元素距离多远）
    step = len(unsorted_list) // group_length
    #步长为1，或列表太短，直接用插入排序；递归出口
    if step == 1 or len(unsorted_list) <= 3:
        return insert_sort(unsorted_list)
    #对每组进行排序
    for x in range(0, step):
        #每组单独进行插入排序，从第二个元素开始，逐个插入到之前的元素中
        for i in range(1, group_length):
            element = unsorted_list[x + i * step]
            for j in range(i - 1, -1, -1):
                if element < unsorted_list[x + j * step]:
                    unsorted_list[x + (j + 1) * step] = unsorted_list[x + j * step]
                    if j == 0:
                        unsorted_list[x] = element
                else:
                    unsorted_list[x + (j + 1) * step] = element
                    break
    return shell_sort(unsorted_list, group_length * 2)

'''
桶排序
@listA 排序列表
@min 排序桶起始值
@max 桶结尾值
@step 每个桶的数据范围
'''
def bucket_sort(unsorted_list, min_value, max_value, step):
    resultList = []     #排序结果数组
    #如果桶范围为0，默认分128个桶
    if step == 0:
        step = (max_value - min_value) // 126
    #取值范围为0，根据列表长度选择插入排序或希尔排序
    if min_value == max_value:
        return insert_sort(unsorted_list) if len(unsorted_list) < 32 else shell_sort(unsorted_list, 2)
    #正常的桶排序
    else:
        #初始化“桶”，前后都预留一个桶，用于放小于最小值和大于最大值的数据
        numOfBuckets = (max_value - min_value) // step + 2
        buckets = [[] for _ in range(numOfBuckets)]
        #数据落入对应范围的桶中
        for element in unsorted_list:
            if element < min_value:
                buckets[0] += [element]
            elif element > max_value:
                buckets[len(buckets) - 1] += [element]
            else:
                buckets[(element - min_value) // step + 1] += [element]
        # 桶内根据元素数量选择插入排序或希尔排序
        for elementList in buckets:
            elementList = insert_sort(elementList) if len(elementList) < 32 \
                else shell_sort(elementList, 2)
            resultList += elementList
    return resultList